CMU 15-112 Summer 2019: Fundamentals of Programming and Computer Science
Homework 9 (Due Thurs 13-Jun, at 5pm)

• This assignment is SOLO. This means you may not look at other student's code or let other students look at your code for these problems. See the syllabus for details.


• To start:
  1. Create a folder named 'week4'
  2. Edit hw9.py using Pyzo. Note that you are not given a starter file. This means you must make your own test cases!
  3. When you are ready, submit hw9.py to Autolab. For this hw you will have 15 submissions.
• This homework is fully autograded.
• Do not hardcode the test cases in your solutions.
• This homework may be graded for style.
• You must use recursion to solve these problems. Using a for or while loop will result in you losing full credit for the question (except for question 5). You may also not use inherently iterative functions. These include range, sum, max, min, count, replace, sort, reverse, sorted, and reversed.
• You should be able to do problems 2, 3 and 4 after Tuesday's lecture, and you'll be able to do problem 5 after Wednesday's lecture (problem 1 is just meeting with your TA for term projects). Start early with the first three problems, since the fourth one is worth 45 pts.

1. Meeting with TA [5 pts]
   Meet with one of your recitation TAs for a preliminary term project idea meeting. This meeting can be done any time before quiz time on Friday.
   
   


2. recursive alternatingSum(lst) [10 pts] [autograded]
   Write the function alternatingSum(lst) that takes a possibly-empty list of numbers, lst, and returns the alternating sum of the list, where every other value is subtracted rather than added. For example: alternatingSum([1,2,3,4,5]) returns 1-2+3-4+5 (that is, 3). If lst is empty, return 0.
   
   


3. recursive binarySearchValues(L, v) [15 pts] [autograded]
   Write the function binarySearchValues(L, v) that takes a sorted list L and a value v and returns a list of tuples, (index, value), of the values that binary search must check to verify whether or not v is in L. As an example, say:

      L = ['a', 'c', 'f', 'g', 'm', 'q']
      v = 'c'
   

   Binary search always searches between some start and end index (exclusive), which initially are 0 and (len(L)). So here, start=0 and end=6. The first index we try, then, is mid=3 (the integer average of start and end). The value there is 'g', so we will add (3, 'g') to our result.
   
   Since 'g' is not the value we are seeking, we continue, only now we are searching from start=0 to end=3, just like we did with Binary Search in class.
   
   Now we try mid=1 (the integer average of start and end), and so we add (1, 'c') to our result. We found 'c', so we're done. And so we see:

       L = ['a', 'c', 'f', 'g', 'm', 'q']
       v = 'c'
       assert(binarySearchValues(L, v) == [(3,'g'), (1,'c')])
   

   
   In the case where v is not in L, still return the list of tuples of indices and values searched. For example:

       L = ['a', 'c', 'f', 'g', 'm', 'q']
       v = 'b'
       assert(binarySearchValues(L, v) == [(3, 'g'), (1, 'c'), (0, 'a')])
   

   
   Hint: Do not slice the list L, but rather adjust the indexes into L.
   Hint Hint: It might help to write a helper function that can take in a start and end index in addition to L and v. This helper function will do all of the work. What should you return when start == end?


4. recursive generateLetterString [25 pts] [autograded]
   Write the function generateLetterString(s) that takes a two-character string and returns a new string that contains the all of the letters between the first letter and the second letter. For example, generateLetterString("ko") would return "klmno". This should also work backwards, so generateLetterString("me") would return "mlkjihgfe". If the initial provided string is not two characters long you should return the empty string. If the string contains two identical characters (like "aa"), then return the letter ("a"). You may assume that you are given only lowercase letters.
   
   


5. solveSudoku(board) [45 pts] [autograded]
   Write the function solveSudoku(board) that takes a partially-completed Sudoku board (a 2d list with 0's representing empty cells), and returns a solved version of the same puzzle, or None if no such solution exists. You may want to make use of code from hw5. If you never completed that code, you should meet with a TA as soon as possible to help you get that code working.
   
   Here is a very simple testing function to help get you started. You will need to test more than this.
   
   
   def testSolveSudoku(): print('Testing solveSudoku()...', end='') board = [ [ 5, 3, 0, 0, 7, 0, 0, 0, 0 ], [ 6, 0, 0, 1, 9, 5, 0, 0, 0 ], [ 0, 9, 8, 0, 0, 0, 0, 6, 0 ], [ 8, 0, 0, 0, 6, 0, 0, 0, 3 ], [ 4, 0, 0, 8, 0, 3, 0, 0, 1 ], [ 7, 0, 0, 0, 2, 0, 0, 0, 6 ], [ 0, 6, 0, 0, 0, 0, 2, 8, 0 ], [ 0, 0, 0, 4, 1, 9, 0, 0, 5 ], [ 0, 0, 0, 0, 8, 0, 0, 7, 9 ] ] solved = solveSudoku(board) solution = [ [5, 3, 4, 6, 7, 8, 9, 1, 2], [6, 7, 2, 1, 9, 5, 3, 4, 8], [1, 9, 8, 3, 4, 2, 5, 6, 7], [8, 5, 9, 7, 6, 1, 4, 2, 3], [4, 2, 6, 8, 5, 3, 7, 9, 1], [7, 1, 3, 9, 2, 4, 8, 5, 6], [9, 6, 1, 5, 3, 7, 2, 8, 4], [2, 8, 7, 4, 1, 9, 6, 3, 5], [3, 4, 5, 2, 8, 6, 1, 7, 9] ] assert(solved == solution) print('Passed!')
   
   Notes/Hints:
   • You must use recursion and backtracking to solve this problem. You may use loops to assist your approach, but your overall approach must still be recursive backtracking.
   • This is a backtracking problem. Study the backtracking template and backtracking examples; they will help.
   • Make sure to return None as soon as you determine that a step has no solutions! Otherwise, the code might take a very long time to run.